package com.datastructure2.linkedlist;

import com.sun.xml.internal.messaging.saaj.soap.ver1_1.Header1_1Impl;

import java.util.HashMap;
import java.util.List;

/**
 * @author: 临晖
 * @date: 2023/12/19
 * @description:
 */

//链表
public class Solution {


    /**
     *
     *203. 移除链表元素
     * 简单
     * 1.4K
     * 相关企业
     * 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
     * @param head
     * @param val
     * @return
     */
    public static ListNode removeElements(ListNode head, int val) {
        ListNode first = new ListNode();
        first.next = head;
        ListNode curr = first;

        while (curr.next != null) {
            if (curr.next.val == val) {
                curr.next = curr.next.next;
            } else {
                curr = curr.next;
            }

        }

        return first.next;
    }


    /**
     *
     * 206. 反转链表
     * 简单
     * 3.4K
     * 相关企业
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        //ListNode curr= null;
        //
        //while (head != null) {
        //    ListNode temp = head.next;
        //    head.next = curr;
        //    curr = head;
        //    head = temp;
        //}
        //
        //return head;

        //递归
        return reverse(head, null);
    }

    public ListNode reverse(ListNode curr, ListNode pre) {
        if (curr == null) {
            return pre;
        }

        ListNode node = curr.next;
        curr.next = pre;
        return reverse(node, curr);


    }


    /**
     *
     * 24. 两两交换链表中的节点
     * 中等
     * 2.1K
     * 相关企业
     * 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
     *
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {

        ListNode first = new ListNode();        //定义虚拟节点
        first.next = head;
        ListNode curr = first;

        while (curr.next != null && curr.next.next != null) {
            ListNode temp = curr.next;
            ListNode temp1 = curr.next.next.next;

            //第一步
            curr.next = curr.next.next;
            curr.next.next = temp;
            temp.next = temp1;
            curr = curr.next.next;

        }

        return first.next;
    }


    /**
     *
     * 19. 删除链表的倒数第 N 个结点
     * 提示
     * 中等
     * 2.8K
     * 相关企业
     * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     *
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode first = new ListNode();
        first.next = head;

        //ListNode curr = first;
        ListNode slow = first;
        ListNode fast = first;
        int count = 0;
        while (fast.next != null) {

            if (count > n - 1) {
                slow = slow.next;
            }

            fast = fast.next;
            count++;

        }

        slow.next = slow.next.next;
        return first.next;
    }


    /**
     *
     * 面试题 02.07. 链表相交
     * 提示
     * 简单
     * 417
     * 相关企业
     * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
     * 图示两个链表在节点 c1 开始相交：
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int countA = 0;
        int countB = 0;

        ListNode currA = headA;
        ListNode currB = headB;
        while (currA != null) {
            countA++;
            currA = currA.next;
        }

        while (currB != null) {
            countB++;
            currB = currB.next;
        }


        currA = headA;
        currB = headB;

        if (countA > countB) {
            int diff = countA - countB;
            for (int i = 0; i < diff; i++) {
                currA = currA.next;
            }
        } else {
            int diff = countB - countA;
            for (int i = 0; i < diff; i++) {
                currB = currB.next;
            }
        }

        while (currA != null) {
            if (currA == currB) {
                return currA;
            }
            currA = currA.next;
            currB = currB.next;
        }

        return null;

    }


    /**
     *
     * 142. 环形链表 II
     * 中等
     * 2.4K
     * 相关企业
     * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
     * 不允许修改 链表。
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        ListNode curr = null;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                curr= fast;
                break;
            }
        }

        if (curr == null) {
            return null;
        }

        while (true) {
            if (head == curr) {
                return head;
            }

            head = head.next;
            curr = curr.next;
        }
    }


    public static void main(String[] args) {
        ListNode temp1 = new ListNode(1);
        ListNode temp2 = new ListNode(2);
        ListNode temp3 = new ListNode(3);
        ListNode temp4 = new ListNode(4);

        temp1.next = temp2;
        temp2.next = temp3;
        temp3.next = temp4;

        Solution so = new Solution();
        so.swapPairs(temp1);
    }





}
